//题号：五、12
#include <iostream>
#include <queue>
#include <stack>
using namespace std;
int **roads;
class Quan{
    public:
    int x;
    int y;
    int length;
    Quan(int x,int y){
        this->x=x;
        this->y=y;
        this->length=roads[x][y];
    }
    bool operator<(Quan &quan) const {
        return this->length<quan.length;
    }
};

int testify(int **A,int N){//测试是否联通

    int visited[N];
    for(int i=0;i<N;i++){
        visited[i]=0;
    }
    int unvisited=0;//编号
    stack<int> path;
    
    path.push(unvisited);
    visited[unvisited]=1;
    while (!path.empty()){
        int index=path.top();
        int next=-1;
        for (int i=0;i<N;i++){
            //当前节点和下一节点有连接，且下一节点未访问，则访问
            if (A[index][i]==1&&!visited[i]){
                next=i;
                break;
            }
        }
        if (next!=-1){
            path.push(next);
            visited[next]=1;
            printf("%d\n",next);//访问该节点
        }
        else{
            path.pop();//当前节点没有可以访问的其他节点了
        }
    }
    unvisited=-1;
    //寻找该图中是否有非联通的部分
    for (int i=0;i<N;i++){
        if (!visited[i]){
            unvisited=i;
            break;
        }
    }
    if (unvisited==-1){
        return 1;//1表示联通
    }
    return 0;//0表示非联通

}    


priority_queue<class Quan> queu;

void mintree(int **roads, int N){
    int count=0;
    for (int i=0; i<N; i++){
        for (int j=i+1; j<N; j++){
            if (roads[i][j]==1){
                queu.push(Quan(i,j));
                count++;
            }
        }
    }
    
    while (count>N-1){
        class Quan temp=queu.top();
        queu.pop();
        roads[temp.x][temp.y]=0;
        roads[temp.y][temp.x]=0;
        int LianTong=testify(roads,N);
        if (!LianTong){
            roads[temp.x][temp.y]=1;
            roads[temp.y][temp.x]=1;
        }
        else {count--;}
    }
    return;
}

